<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8"> <meta name="viewport" content="width=device-width">
    <title>23树的一种删除方法</title>
    <meta name="viewport" content="width=device-width,initial-scale=1, shrink-to-fit=no">
    <!-- Bootstrap CSS -->
    <link rel="stylesheet"
          href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/css/bootstrap.min.css"
          integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk"
          crossorigin="anonymous">
    <link rel="stylesheet"
          href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/androidstudio.min.css">
<!--    <link rel="stylesheet" href="/web_template_css.css">-->
    <!-- this is highlight.js -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async
            src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.slim.min.js"
    integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js"
    integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/js/bootstrap.min.js"
    integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
    <style>
      img{
        display: block;
        height: auto;
        max-width: 100%;
      }
    </style>
  </head>
  <body>
    <nav class="navbar navbar-expand-lg navbar-light bg-light">
        <a class="navbar-brand" href="#">kvrmnks</a>
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
          <span class="navbar-toggler-icon"></span>
        </button>
        <div class="collapse navbar-collapse" id="navbarNav">
          <ul class="navbar-nav">
            <li class="nav-item active">
              <a class="nav-link" href="./../../../../../index.html" target="_self">Home <span class="sr-only">(current)</span></a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../blog.html">Blog</a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../about.html">About</a>
            </li>
          </ul>
        </div>
      </nav>



    <div class='container'>
      <h3>23树的一种删除方法</h3>

<p>似乎网上没有什么对于23树删除时候的教程</p>

<p>即使是有的那些也是躲躲闪闪，不讲个明白，本文尽我最大的可能将这个操作讲明白（最后还是鸽了</p>

<p>不同于本人的别的blog，这次本人花巨资画了示意图（</p>

<p>但是这个blog别人也看不到呀（（</p>

<h4>参考资料</h4>

<p><a href="https://www.cs.drexel.edu/%7Eamd435/courses/cs260/lectures/L-6_2-3_Trees.pdf">网上的2-3树教程</a></p>

<p>挺可惜的是这篇2-3树有两种删除时候的情况没有讨论，可能是太简单了吧（</p>

<h4>删除</h4>

<h5>分析大纲</h5>

<p>为了保证排版我用缩进简单介绍一下思路</p>

<pre><code class="language-cpp">删除的是非叶子结点
    
删除的是叶子结点
    删除的是3type结点
    
    删除的是2type结点
        2type结点的父亲是2type结点
            2type结点的兄弟是2type结点
            2type结点的兄弟是3type结点
    
        2type结点的父亲是3type结点
            2type结点存在一个兄弟是2type结点
            2type结点存在一个兄弟是3type结点
</code></pre>

<p>首先我们要删除一个结点的话。</p>

<p>我们要找到那个结点在哪里。</p>

<p>我们首先根据删除结点的情况进行分类。</p>

<ol>
<li><p>要删除的结点不是叶子结点</p></li>
<li><p>要删除的结点是叶子结点</p></li>
</ol>

<hr>

<h5>删除的不是叶子结点</h5>

<p>这时候我们找到这个结点的后继，然后把后继的值和要删除结点的值swap一下。</p>

<p>然后只需要删除后继就好了。</p>

<p>那...为什么要这么做呢，一来这样依旧能够保证整棵树的中序遍历的正确性。</p>

<p>此外这个结点的后继一定是一个叶子！我们接下来就来证明这个结论。</p>

<hr>

<h6>一个非叶子结点的后继一定是一个叶子</h6>

<p>如果你学过其他的种类的平衡树的话，你会发现这个性质是一般平衡树所没有的。</p>

<p>例如</p>

<p><img src="../23树的一种删除方法/image-20201118150619932.png" alt="image-20201118150619932" style="zoom:33%;" /></p>

<p>其中5结点的后继6就不是一个叶子</p>

<p>原因在于5的后继可能有右儿子，但是在2-3树中保证了除叶子节点外，每个分支节点的儿子数量是满的，于是意味着一个结点一旦有儿子，则一定有很多儿子，这个它是一个后继相矛盾，可以自己想想。</p>

<hr>

<h6>一个非叶子结点的后继一定在右儿子中</h6>

<p>这个也是普通平衡树所没有的性质。</p>

<p>举个栗子。</p>

<p><img src="../23树的一种删除方法/image-20201118151254501.png" alt="image-20201118151254501" style="zoom:33%;" /></p>

<p>考虑5的后继，显然得到了后继不一定在右儿子中的结论。</p>

<p>由于2-3保证了所有分支结点一定有多个儿子，于是证明显然。</p>

<p>有了以上两条性质的保证。我们就可以知道经过上面两个步骤，一个删除非叶子结点的操作，被转化成了一个删除叶子结点的操作。</p>

<hr>

<h5>删除的是叶子结点</h5>

<p>于是本质上只有删除的是叶子结点的操作。</p>

<p>我们考虑接着来分析问题</p>

<hr>

<h5>删除的是3type结点</h5>

<p>由于这个叶子结点有多个值，直接删掉那个，然后把这个结点改成2type结点就好了。</p>

<p>举个栗子。</p>

<p><img src="../23树的一种删除方法/image-20201118151957245.png" alt="image-20201118151957245" style="zoom:50%;" /></p>

<hr>

<h5>删除的是2type结点</h5>

<p>这个时候我们肯定不能直接把这个结点删了，不然树就不一样高了。</p>

<p>于是我们只能寻求它的父亲或者兄弟的帮助。</p>

<p>继续进行分类讨论</p>

<ol>
<li>2type结点的父亲是3type结点</li>
<li>2type结点的父亲是2type结点</li>
</ol>

<hr>

<h5>2type结点的父亲是2type结点 且有一个3type兄弟</h5>

<p><img src="../23树的一种删除方法/image-20201118154111402.png" alt="image-20201118154111402" style="zoom:50%;" /></p>

<p>其中A代表被删除的叶子，这样调整一下顺序就完成了调整过程。</p>

<hr>

<h5>2type结点的父亲是2type结点 且有一个2type兄弟</h5>

<p><img src="../23树的一种删除方法/image-20201118154234502.png" alt="image-20201118154234502" style="zoom:50%;" /></p>

<p>A是要被删除的结点，经过这样的调整，把A拉到了最上面，但是并没有完全处理完成，需要继续向上递归，不过我们先完成对删除叶子一步的操作，之后我们再统一讨论如果递归地处理。</p>

<hr>

<h5>2type结点的父亲是3type结点 且有一个兄弟是2type结点</h5>

<p><img src="../23树的一种删除方法/image-20201118154552126.png" alt="image-20201118154552126" style="zoom:50%;" /></p>

<p>删除A结点，只需要将B和C压成一个结点并且把父亲变成2type就好了，再次注意这里A是个叶子，A是子树的情况之后再讨论</p>

<hr>

<h5>2type结点的父亲是3type结点 且有一个兄弟是3type结点</h5>

<p><img src="../23树的一种删除方法/image-20201118154730391.png" alt="image-20201118154730391" style="zoom:50%;" /></p>

<p>思路类似在此不再赘述。</p>

<hr>

<h5>对于递归处理的讨论</h5>

<p>可以发现对于删除A这个叶子的一步操作中只有**2type结点的父亲是2type结点 且有一个2type兄弟**这种情况下，我们必须要进行向上递归处理。</p>

<p>观察这个时候，向上处理时\(A\)是一颗子树，且之后一个儿子，这个性质非常关键。</p>

<p>事实上下面的讨论与上面的讨论的区别就在于，被删除的结点A从一个叶子，变成了一个只有一个儿子的且根为A的子树的根。</p>

<p><img src="../23树的一种删除方法/image-20201118155324487.png" alt="image-20201118155324487" style="zoom:50%;" /></p>

<p>递归时A也会遇到</p>

<ol>
<li>2type结点的父亲是2type结点 且有一个3type兄弟</li>
<li>2type结点的父亲是2type结点 且有一个2type兄弟</li>
<li>2type结点的父亲是3type结点 且有一个兄弟是2type结点</li>
<li>2type结点的父亲是3type结点 且有一个兄弟是3type结点</li>
</ol>

<p>这4种情况</p>

<hr>

<h5>2type结点的父亲是2type结点 且有一个3type兄弟</h5>

<p>由于现在A不再是叶子了，于是讨论要加上子树。</p>

<p>调整如图</p>

<p><img src="../23树的一种删除方法/image-20201118155625467.png" alt="image-20201118155625467" style="zoom: 50%;" /></p>

<hr>

<h5>2type结点的父亲是2type结点 且有一个2type兄弟</h5>

<p>调整方式如下，可以发现这种情况下还需要继续向上递归</p>

<p><img src="../23树的一种删除方法/image-20201118160237367.png" alt="image-20201118160237367" style="zoom:50%;" /></p>

<hr>

<h5>2type结点的父亲是3type结点 且有一个兄弟是2type结点</h5>

<p>调整方式如下</p>

<p><img src="../23树的一种删除方法/image-20201118160424937.png" alt="image-20201118160424937" style="zoom: 50%;" /></p>

<hr>

<h5>2type结点的父亲是3type结点 且有一个兄弟是3type结点</h5>

<p>调整方法如下</p>

<p><img src="../23树的一种删除方法/image-20201118160606692.png" alt="image-20201118160606692" style="zoom:50%;" /></p>

<hr>

<p>综合以上3种情况，可以发现还是只有一种情况需要继续向上递归，这时依旧满足子书中只有一个儿子，于是可以继续上面的过程</p>

<p>最终要么终止于没有父亲，要么终止于其他3种情况</p>

<h5>递归过程中没有父亲</h5>

<p>这时需要重新指定整个2-3树的根</p>

<p><img src="../23树的一种删除方法/image-20201118160853859.png" alt="image-20201118160853859" style="zoom:50%;" /></p>

<hr>

<p>完结散花（</p>

<p>贴个代码吧</p>

<pre><code class="language-cpp">#include &lt;iostream&gt;
#include &lt;algorithm&gt;
#include &lt;cassert&gt;
using namespace std;
template&lt;typename T&gt;
class _23Tree{
private:
    struct Node{
        Node *ch[4], *fa;
        T data[3];
        unsigned int height;
        bool isThree;
    };
    Node *createNode();
    Node *root;
    void maintain(Node *x);
    void erase_maintain(Node *);
    void _display(Node *x);
    Node *_find(T);
public:
    _23Tree();
    unsigned int getHeight()const;
    void insert(T);
    void erase(T);
    bool find(T);
    void display();
};

template&lt;typename T&gt;
_23Tree&lt;T&gt;::_23Tree(){
    root = nullptr;
}

template&lt;typename T&gt;
typename _23Tree&lt;T&gt;::Node *_23Tree&lt;T&gt;::createNode(){
    Node *t = new Node();
    // clear node
    for(int i = 0; i &lt; 3; i++)t-&gt;ch[i] = nullptr;
    t-&gt;fa = nullptr;
    t-&gt;height = 0;
    t-&gt;isThree = false;
    return t;
}

template&lt;typename T&gt;
void _23Tree&lt;T&gt;::maintain(_23Tree&lt;T&gt;::Node *x){
    // maintain for a single tree
    // whose father is to be inserted
    // initially x&#39;s father exists
    Node *y = x-&gt;fa;
    if(y-&gt;isThree){
        // when x&#39;s father is 3-type

        //find the loc
        int ch_loc = 0;
        for(int i = 0; i &lt; 3 ; i++){
            if(y-&gt;ch[i] == x) {
                ch_loc = i;
                break;
            }
        }

        //insert the pointers into y
        for(int i = 3; i &gt; ch_loc; i--){
            y-&gt;ch[i] = y-&gt;ch[i - 1];
        }
        y-&gt;ch[ch_loc] = x-&gt;ch[0];
        y-&gt;ch[ch_loc+1] = x-&gt;ch[1];
        for(int i = 0 ; i &lt; 4; i++){
            y-&gt;ch[i]-&gt;fa = y;
        }

        //insert data into y
        y-&gt;data[2] = x-&gt;data[0];
        sort(y-&gt;data, y-&gt;data+3);

        //split y
        Node *tmp = createNode();
        Node *p1 = createNode();
        Node *p2 = createNode();
        tmp-&gt;data[0] = y-&gt;data[1];
        p1-&gt;data[0] = y-&gt;data[0];
        p2-&gt;data[0] = y-&gt;data[2];

        p1-&gt;ch[0] = y-&gt;ch[0];
        p1-&gt;ch[1] = y-&gt;ch[1];
        p2-&gt;ch[0] = y-&gt;ch[2];
        p2-&gt;ch[1] = y-&gt;ch[3];
        p1-&gt;fa  = p2-&gt;fa = tmp;
        p1-&gt;ch[0]-&gt;fa = p1-&gt;ch[1]-&gt;fa = p1;
        p2-&gt;ch[0]-&gt;fa = p2-&gt;ch[1]-&gt;fa = p2;
        tmp-&gt;ch[0] = p1;
        tmp-&gt;ch[1] = p2;
        p1-&gt;height = p2-&gt;height = y-&gt;height;
        tmp-&gt;height = p1-&gt;height + 1;

        // exchange y&#39;s father
        Node *z = y-&gt;fa;
        tmp-&gt;fa = z;
        if(z == nullptr){
            root = tmp;
        }else{
            int child_size = z-&gt;isThree ? 3 : 2;
            for(int i=0;i&lt;child_size ;i++){
                if(z-&gt;ch[i] == y){
                    child_size = i;
                    break;
                }
            }
            z-&gt;ch[child_size] = tmp;
            delete y;
            maintain(tmp);
        }

    }else{
        // when x&#39;s father is 2-type
        y-&gt;isThree = true;
        //find the loc
        int ch_loc = 0;
        for(int i = 0; i &lt; 2; i++){
            if(y-&gt;ch[i] == x){
                ch_loc = i;
                break;
            }
        }
        ch_loc ^= 1;

        // insert the pointer into y
        if(ch_loc == 0){
            y-&gt;ch[1] = x-&gt;ch[0];
            y-&gt;ch[2] = x-&gt;ch[1];
        }else{
            y-&gt;ch[2] = y-&gt;ch[1];
            y-&gt;ch[0] = x-&gt;ch[0];
            y-&gt;ch[1] = x-&gt;ch[1];
        }
        for(int i=0;i&lt;3;i++){
            y-&gt;ch[i]-&gt;fa = y;
        }

        //insert the data into y
        y-&gt;data[1] = x-&gt;data[0];
        std::sort(y-&gt;data, y-&gt;data+2);
        delete x;
    }
}

template&lt;typename T&gt;
unsigned int _23Tree&lt;T&gt;::getHeight()const{
    return root-&gt;height;
}

template&lt;typename T&gt;
void _23Tree&lt;T&gt;::insert(T x){
    Node *cur = root;
    if(cur == nullptr){
        root = createNode();
        root-&gt;data[0] = x;
        return;
    }
    Node *y = cur;
    while(cur != nullptr){
        int R = cur-&gt;isThree ? 2 : 1;
        int i;
        for(i = 0; i &lt; R; i++){
            if(cur -&gt; data[i] &lt; x){
//                break;
            }else{
                break;
            }
        }
//        i = min(i, R-1);
        y = cur;
        cur = cur-&gt;ch[i];
    }
    if(y-&gt;isThree){
        //insert new node
        y-&gt;data[2] = x;
        std::sort(y-&gt;data, y-&gt;data+3);

        // cur is y&#39;s father
        cur = y-&gt;fa;

        // split 4-type node
        Node *tmp = createNode();
        Node *p1 = createNode();
        Node *p2 = createNode();
        p1-&gt;data[0] = y-&gt;data[0];
        tmp-&gt;data[0] = y-&gt;data[1];
        p2-&gt;data[0] = y-&gt;data[2];
        tmp-&gt;ch[0] = p1;
        tmp-&gt;ch[1] = p2;
        p1-&gt;fa = tmp;
        p2-&gt;fa = tmp;
        tmp-&gt;height = 1;
        tmp-&gt;fa = y-&gt;fa;

        //exchange cur&#39;s son to the new 3 node
            //when father is nullptr
        if(cur == nullptr){
            root = tmp;
            delete y;
            return;
        }
            //when father exists
        int child_size = (cur-&gt;isThree ? 3 : 2);
        for(int i = 0; i &lt; child_size; i++){
            if(cur -&gt; ch[i] == y){
                child_size = i;
                break;
            }
        }
        cur-&gt;ch[child_size] = tmp;
        tmp-&gt;fa = cur;
        delete y;

        //update recursively
        maintain(tmp);

    }else{
        y-&gt;data[1] = x;
        std::sort(y-&gt;data, y-&gt;data+2);
        y-&gt;isThree = true;
    }
}

template&lt;typename T&gt;
void _23Tree&lt;T&gt;::erase(T v) {
    Node *x = _find(v);
    if(x == nullptr) return;
    if(x-&gt;ch[0] == nullptr){
        // x is leaf
        if(x-&gt;isThree){
            int child_size = x-&gt;isThree ? 2 : 1;
            x-&gt;isThree = false;
            int loc = 0;
            for(loc = 0; loc &lt; child_size; loc++){
                if(x-&gt;data[loc] != v)break;
            }
            swap(x-&gt;data[loc], x-&gt;data[0]);
            x-&gt;data[1] = T{};
        }else{
            erase_maintain(x);
        }
    }else{
        // x is not leaf
        int loc = 0;
        int child_size = x-&gt;isThree ? 2 : 1;
        for(loc = 0; loc &lt; child_size; loc ++){
            if(x-&gt;data[loc] == v)break;
        }
        assert(loc &lt; child_size);

        // find next in InOrder
        Node *y = x-&gt;ch[loc + 1];
        while(y-&gt;ch[0] != nullptr)
            y = y-&gt;ch[0];
        x-&gt;data[loc] = y-&gt;data[0];

        if(y-&gt;isThree){
            int child_size = y-&gt;isThree ? 2 : 1;
            y-&gt;isThree = false;
            swap(y-&gt;data[1], y-&gt;data[0]);
            y-&gt;data[1] = T{};
        }else{
            erase_maintain(y);
        }

    }

}

template&lt;typename T&gt;
bool _23Tree&lt;T&gt;::find(T v) {
    return (_find(v) != nullptr);
}

template&lt;typename T&gt;
void _23Tree&lt;T&gt;::display() {
    _display(root);
}

template&lt;typename T&gt;
void _23Tree&lt;T&gt;::_display(_23Tree::Node *x) {
//    cout &lt;&lt; x &lt;&lt; endl;
    if(x == nullptr) return;

    int child_size = x-&gt;isThree ? 2 : 1;
    //son list
    _display(x-&gt;ch[0]);
    for(int i=0;i&lt;child_size;i++){
        cout &lt;&lt; x-&gt;data[i] &lt;&lt; &quot; &quot; &lt;&lt; x-&gt;height &lt;&lt; endl;
        _display(x-&gt;ch[i+1]);
    }
}

template&lt;typename T&gt;
typename _23Tree&lt;T&gt;::Node *_23Tree&lt;T&gt;::_find(T v) {
    Node *x = this-&gt;root;
    while(x != nullptr){
        int child_size = x-&gt;isThree ? 2 : 1;
        bool flag = false;
        for(int i=0;i&lt;child_size;i++){
            if(x-&gt;data[i] == v)flag = true;
        }
        if(flag) break;
        int i = 0;
        for(i=0;i&lt;child_size;i++){
            if(v &lt; x-&gt;data[i])break;
        }
        x = x-&gt;ch[i];
    }
    return x;
}

template&lt;typename T&gt;
void _23Tree&lt;T&gt;::erase_maintain(_23Tree::Node *x) {
    int child_size = x-&gt;isThree ? 2 : 1;
    // x is 2-type node
    Node *y = x-&gt;fa;
    if(y == nullptr){
        // when father doesn&#39;t exist
        root = x-&gt;ch[1];
    }else{
        // when father exists

        //find x&#39;s location in y
        child_size = y-&gt;isThree ? 2 : 1;
        int loc = -1;
        for(int i=0; i&lt;= child_size; i++){
            if(y-&gt;ch[i] == x){
                loc = i;
                break;
            }
        }
        assert(loc != -1);

        if(y -&gt; isThree){
            // father is 3-type node
            int to = 0;
            if(loc == 0)to = 1;
            if(loc == 1)to = 2;
            if(loc == 2)to = 1;
            Node *w = y-&gt;ch[to];
            if(w-&gt;isThree){
                if(loc == 0){
                    if(x-&gt;ch[0] == nullptr) x-&gt;ch[0] = x-&gt;ch[1];
                    x-&gt;data[0] = y-&gt;data[0];
                    y-&gt;data[0] = w-&gt;data[0];
                    w-&gt;data[0] = w-&gt;data[1];
                    w-&gt;data[1] = T{};
                    w-&gt;isThree = false;
                    x-&gt;ch[1] = w-&gt;ch[0];
                    for(int i=0;i&lt;=1;i++)w-&gt;ch[i] = w-&gt;ch[i+1];
                    w-&gt;ch[2] = nullptr;
                    if(x-&gt;ch[1]!=nullptr)x-&gt;ch[1]-&gt;fa = x;
                }else if(loc == 1){
                    if(x-&gt;ch[0] == nullptr) x-&gt;ch[0] = x-&gt;ch[1];
                    x-&gt;data[0] = y-&gt;data[1];
                    y-&gt;data[1] = w-&gt;data[0];
                    w-&gt;data[0] = w-&gt;data[1];
                    w-&gt;data[1] = T{};
                    w-&gt;isThree = false;
                    x-&gt;ch[1] = w-&gt;ch[0];
                    for(int i=0;i&lt;=1;i++)w-&gt;ch[i] = w-&gt;ch[i+1];
                    w-&gt;ch[2] = nullptr;
                    if(x-&gt;ch[1]!=nullptr)x-&gt;ch[1]-&gt;fa = x;
                }else{
                    if(x-&gt;ch[1] == nullptr) x-&gt;ch[1] = x-&gt;ch[0];
                    x-&gt;data[0] = y-&gt;data[1];
                    y-&gt;data[1] = w-&gt;data[1];
                    w-&gt;data[1] = T{};
                    w-&gt;isThree = false;
                    x-&gt;ch[0] = w-&gt;ch[2];
                    w-&gt;ch[2] = nullptr;
                    if(x-&gt;ch[0]!=nullptr)x-&gt;ch[0]-&gt;fa = x;
                }
            }else{
                if(loc == 0){
                    w-&gt;isThree = true;
                    w-&gt;data[1] = w-&gt;data[0];
                    w-&gt;data[0] = y-&gt;data[0];
                    y-&gt;data[0] = y-&gt;data[1];
                    y-&gt;data[1] = T{};
                    y-&gt;isThree = false;
                    for(int i=0;i&lt;=1;i++)y-&gt;ch[i] = y-&gt;ch[i+1];
                    y-&gt;ch[2] = nullptr;
                    for(int i=1;i&gt;=0;i--)w-&gt;ch[i+1] = w-&gt;ch[i];
                    w-&gt;ch[0] = x-&gt;ch[0]==nullptr ? x-&gt;ch[1] : x-&gt;ch[0];
                    for(int i=0;i&lt;=2;i++)if(w-&gt;ch[i]!=nullptr)w-&gt;ch[i]-&gt;fa = w;
                    delete x;
                }else if(loc == 1){
                    w-&gt;isThree = true;
                    w-&gt;data[1] = w-&gt;data[0];
                    w-&gt;data[0] = y-&gt;data[1];
                    y-&gt;data[1] = T{};
                    y-&gt;isThree = false;
                    y-&gt;ch[1] = y-&gt;ch[2];
                    y-&gt;ch[2] = nullptr;
                    for(int i=1;i&gt;=0;i--)w-&gt;ch[i+1] = w-&gt;ch[i];
                    w-&gt;ch[0] = x-&gt;ch[0]==nullptr ? x-&gt;ch[1] : x-&gt;ch[0];
                    for(int i=0;i&lt;=2;i++)if(w-&gt;ch[i]!=nullptr)w-&gt;ch[i]-&gt;fa = w;
                    delete x;
                }else{
                    w-&gt;isThree = true;
                    w-&gt;data[1] = y-&gt;data[1];
                    y-&gt;data[1] = T{};
                    y-&gt;isThree = false;
                    y-&gt;ch[2] = nullptr;
                    w-&gt;ch[2] = x-&gt;ch[0]==nullptr ? x-&gt;ch[1] : x-&gt;ch[0];
                    for(int i=0;i&lt;=2;i++)if(w-&gt;ch[i]!=nullptr)w-&gt;ch[i]-&gt;fa = w;
                    delete x;
                }
            }
        }else{
            // father is 2-type node
            Node* w = y-&gt;ch[loc^1];
            if(w-&gt;isThree){
                w-&gt;isThree = false;
                if(loc == 1){
                    x-&gt;data[0] = y-&gt;data[0];
                    y-&gt;data[0] = w-&gt;data[1];
                    w-&gt;data[1] = T{};
                    if(x-&gt;ch[1] == nullptr) x-&gt;ch[1] = x-&gt;ch[0];
                    x-&gt;ch[0] = w-&gt;ch[2];
                    w-&gt;ch[2] = nullptr;
                    if(x-&gt;ch[0] != nullptr)x-&gt;ch[0]-&gt;fa = x;
                }else{
                    x-&gt;data[0] = y-&gt;data[0];
                    y-&gt;data[0] = w-&gt;data[0];
                    w-&gt;data[0] = w-&gt;data[1];
                    w-&gt;data[1] = T{};
                    if(x-&gt;ch[0] == nullptr) x-&gt;ch[0] = x-&gt;ch[1];
                    x-&gt;ch[1] = w-&gt;ch[0];
                    w-&gt;ch[0] = w-&gt;ch[1];
                    w-&gt;ch[1] = w-&gt;ch[2];
                    w-&gt;ch[2] = nullptr;
                    if(x-&gt;ch[1] != nullptr)x-&gt;ch[1]-&gt;fa = x;
                }
            }else{
                w-&gt;isThree = true;
                w-&gt;data[1] = y-&gt;data[0];
                //y-&gt;data[0] = 20000526;
                sort(w-&gt;data, w-&gt;data+2);
                if(x-&gt;ch[0] == nullptr) x-&gt;ch[0] = x-&gt;ch[1];
                if(loc == 0){
                    w-&gt;ch[2] = w-&gt;ch[1];
                    w-&gt;ch[1] = w-&gt;ch[0];
                    w-&gt;ch[0] = x-&gt;ch[0];
                    if(w-&gt;ch[0] != nullptr)w-&gt;ch[0]-&gt;fa = w;
                }else{
                    w-&gt;ch[2] = x-&gt;ch[0];
                    if(w-&gt;ch[2] != nullptr)w-&gt;ch[2]-&gt;fa = w;
                }
                y-&gt;ch[loc] = nullptr;
                delete x;
                erase_maintain(y);
            }
        }
    }

}

int data[100000];
int main(int argc, char **argv){
//    freopen(&quot;1.txt&quot;,&quot;w&quot;,stdout);
    srand(0);
    _23Tree&lt;int&gt; x;
    int n = 20;
    for(int i=1;i&lt;=n;i++)
        data[i] = i;
    random_shuffle(data+1, data+1+n);
    for(int i=1;i&lt;=n;i++){
        x.insert(data[i]);
    }

    for(int i=1;i&lt;=n/4;i++){
        x.erase(data[i]);
        cout &lt;&lt; &quot;erase &quot; &lt;&lt; data[i] &lt;&lt; endl;
//        x.display();
    }
    x.display();
    cout &lt;&lt; x.getHeight() &lt;&lt; endl;
    return 0;
}
</code></pre>


    </div>
    <script>
      hljs.initHighlightingOnLoad()
    </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlightjs-line-numbers.js/2.5.0/highlightjs-line-numbers.min.js"></script>
  <script>
      hljs.initHighlightingOnLoad();
      hljs.initLineNumbersOnLoad();
  </script>
  </body>
</html>